package LeetCode;

public class LC_086_PartitionList {
    public static void main(String[] args) {

    }


    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    static class Solution {
        public ListNode partition(ListNode head, int x) {
            ListNode preHead = new ListNode(0);
            preHead.next = head;
            ListNode pre = preHead;
            ListNode cur = head;
            ListNode insertPos = null;
            while (cur != null) {
                //定位需要插入的位置;
                if (cur.val >= x && insertPos == null) insertPos = pre;
                //插入操作;
                if (cur.val < x && insertPos != null) {
                    pre.next = pre.next.next;
                    cur.next = insertPos.next;
                    insertPos.next = cur;
                    insertPos = insertPos.next;
                    cur = pre.next;
                    continue;
                }
                pre = pre.next;
                cur = cur.next;
            }
            return preHead.next;
        }
    }
}
